
// Constructor - Create a dancing link of size row x col.
function DancingLink(row, col)
{
	this.home = new DancingLink.Header(-1, -1); // sentinel for the whole table
	this.enumerated = true;

	this.rowCount = row;
	this.colCount = col;

	// These are not static values. They should be re-enumerated if the table size changes.
	this.rowHeaders = [];
	this.colHeaders = [];

	var last = this.home;
	for (var i = 0; i < col; i++)
	{
		var current = new DancingLink.Header(-1, i);

		current.left = last;
		last.right = current;

		current.up = current;
		current.down = current;

		last = current;
		this.colHeaders.push(current);
	}
	this.home.left = last;
	last.right = this.home;

	var last = this.home;
	for (var i = 0; i < row; i++)
	{
		var current = new DancingLink.Header(i, -1);

		current.up = last;
		last.down = current;

		current.left = current;
		current.right = current;

		last = current;
		this.rowHeaders.push(current);
	}
	this.home.up = last;
	last.down = this.home;
}

// Class representing a cell/node in Dancing Links (a sparce table)
DancingLink.Node = function (initValue)
{
	this.up = null;
	this.down = null;
	this.left = null;
	this.right = null;

	this.colHeader = null;
	this.rowHeader = null;

	this.value = initValue;
}

// Header class (sentinel for each row/column)
DancingLink.Header = function (r, c)
{
	this.up = null;
	this.down = null;
	this.left = null;
	this.right = null;

	// These are not static values. They should be re-enumerated if the table size changes.
	this.row = r;
	this.col = c;

	this.count = 0;
}

DancingLink.prototype = 
{
	// Since dancing link tables do not have static table dimensions,
	// we need some way to keep track of the cell coordinates.
	// The following functions would enumerate the rows and columns. 
	// Enumeration should be performed before a function attempts to use cell coordinate reference.
	// For build-in functions, this is done automatically.

	enumerate : function ()
	{
		if (!this.enumerated)
		{
			this.enumerateRows();
			this.enumerateCols();
			this.enumerated = true;
		}
	},

	enumerateCols : function ()
	{
		var colCount = 0, HeaderArray = [];
		for (var pos = this.home.right; pos !== this.home; pos = pos.right)
		{
			pos.row = -1;
			pos.col = colCount;
			HeaderArray.push(pos);

			//console.log('Enumerating ' + pos.col + ' col');
			colCount++;
		}
		this.colCount = colCount;
		this.colHeaders = HeaderArray;
		//console.log('Enumerated ' + colCount + ' col');
	},

	enumerateRows : function ()
	{
		var rowCount = 0, HeaderArray = [];
		for (var pos = this.home.down; pos !== this.home; pos = pos.down)
		{
			pos.row = rowCount;
			pos.col = -1;
			HeaderArray.push(pos);

			//console.log('Enumerating ' + pos.row + ' row');

			rowCount++;
		}
		this.rowCount = rowCount;
		this.rowHeaders = HeaderArray;
		//console.log('Enumerated ' + rowCount + ' rows');
	},

	// retrieve the column header of a particular column
	getCol : function (c)
	{
		this.enumerate();
		return this.colHeaders[c];
	},

	// retrieve the row header of a particular row
	getRow : function (r)
	{
		this.enumerate();
		return this.rowHeaders[r];
	},

	toString : function ()
	{
		this.enumerate();

		var s = '';
		for (var rowHeader = this.home.down; rowHeader !== this.home; rowHeader = rowHeader.down)
		{
			var pos = rowHeader.right, col = 0;
			while (pos !== rowHeader)
			{
				if (col < pos.colHeader.col)
				{
					s += ' ';
				}
				else
				{
					//console.log('appending ' + pos.row + ', ' + pos.col)
					s += pos.value;
					pos = pos.right;
				}
				col++;
			}
			while (col < this.colCount)
			{
				s += ' ';
				col++;
			}
			s += '\n';
		}

		return s;
	},

	// The follow functions remove a row/col/cell from the table. 
	// The cell object is permenantly lost if the link is kept elsewhere. 
	removeRow : function (r)
	{
		var rowHeader = this.getRow(r);
		for (var pos = rowHeader.right; pos !== rowHeader; pos = pos.right)
		{
			pos.up.down = pos.down;
			pos.down.up = pos.up;
		}
		rowHeader.up.down = rowHeader.down;
		rowHeader.down.up = rowHeader.up;

		this.rowCount--;
		this.enumerated = false;
		return rowHeader;
	},

	removeCol : function (c)
	{
		var colHeader = this.getCol(c);
		for (var pos = colHeader.down; pos !== colHeader; pos = pos.down)
		{
			pos.left.right = pos.right;
			pos.right.left = pos.left;
		}
		colHeader.left.right = colHeader.right;
		colHeader.right.left = colHeader.left;

		this.colCount--;
		this.enumerated = false;

		return colHeader;
	},

	remove : function (node)
	{
		if (!node) return;

		node.rowHeader.count--;
		node.colHeader.count--;

		node.up.down = node.down;
		if (node.down) node.down.up = node.up;

		node.left.right = node.right;
		if (node.right) node.right.left = node.left;
	},

	// Insert a node into the table. 
	// NOTE: This function doesn't perform the entire operation, instead it links neighboring nodes. 
	insert : function (node, up_neighbor, left_neighbor, rowHeader, colHeader)
	{
		rowHeader.count++;
		colHeader.count++;

		// set node's left_neighbor right
		node.left = left_neighbor;
		node.up = up_neighbor;
		node.colHeader = colHeader;
		node.rowHeader = rowHeader;

		if (left_neighbor.right)
		{
			node.right = left_neighbor.right;
			left_neighbor.right.left = node;
		}
		if (up_neighbor.down)
		{
			node.down = up_neighbor.down;
			up_neighbor.down.up = node;
		}

		left_neighbor.right = node;
		up_neighbor.down = node;
	},

	get : function  (r, c)
	{
		if (!this.getCol(c)) return; // column is out of bound

		for (var pos = this.getCol(c); pos.down; pos = pos.down)
		{
			if (pos.row === r) return pos.value;
			if (pos.row > r) return 0;
		}
		return 0;
	},

	set : function (r, c, value)
	{
		// find up_neighbor
		var colHeader = this.getCol(c);
		//console.log('col ' + colHeader.col);
		for (var up_neighbor = colHeader.up; up_neighbor !== colHeader; up_neighbor = up_neighbor.up)
		{
			// takes care of cells that already exist
			if (up_neighbor.rowHeader.row === r)
			{
				if (value === 0) this.remove (up_neighbor);
				else up_neighbor.value = value;
				return;
			}
			if (up_neighbor.rowHeader.row < r) break;
		}
		// If we did not find the cell in the above operations, then we do not need ot delete it.
		if (value === 0) return;

		// find left_neighbor
		var rowHeader = this.getRow(r);
		for (var left_neighbor = rowHeader.left; left_neighbor !== rowHeader; left_neighbor = left_neighbor.left)
		{
			if (left_neighbor.colHeader.col < c) break;
		}

		this.insert(new DancingLink.Node(value), up_neighbor, left_neighbor, rowHeader, colHeader);
	},

	// ==================== Start of Knuth's Algorithm X ====================
	// The following functions are my implementations of Knuth's Algorithm X.
	// http://en.wikipedia.org/wiki/Algorithm_X

	// The DLX reduction method prescribed by Algo X
	// In terms Sudoku, 
	//     Delink a constraint (column) and any assoicated candidates (row).
	cover : function (colHeader)
	{
		// console.log('Covering column ' + colHeader.col);
		colHeader.right.left = colHeader.left;
		colHeader.left.right = colHeader.right;

		for(var pos = colHeader.down; pos !== colHeader; pos = pos.down)
			for(var rowpos = pos.right; pos !== rowpos; rowpos = rowpos.right)
			{
				rowpos.up.down = rowpos.down;
				rowpos.down.up = rowpos.up;
				if (rowpos.colHeader)
					rowpos.colHeader.count--;
			}
		this.enumerated = false;
		return colHeader;
	},

	// The DLX backtracking method prescribed by Algo X
	// In terms Sudoku,
	//     Relink a constraint (column) and any assoicated candidates (row).
	uncover : function (colHeader)
	{
		// console.log('Uncovering column ' + colHeader.col);
		colHeader.left.right = colHeader;
		colHeader.right.left = colHeader;

		for(var pos = colHeader.down; pos !== colHeader; pos = pos.down)
			for(var rowpos = pos.right; pos !== rowpos; rowpos = rowpos.right)
			{
				rowpos.up.down = rowpos;
				rowpos.down.up = rowpos;
				if (rowpos.colHeader)
					rowpos.colHeader.count++;
			}
		this.enumerated = false;
	},

	// The deterministic column selection method prescribed by Algo X
	// Loop through all uncovered columns, finding the column with the smallest count
	chooseCol : function ()
	{
		var LowCount = this.rowCount + 1;
		var LowCountCol = null;

		// console.log('start: ' + LowCount);
		// for (var pos = this.home.right; pos !== this.home; pos = pos.right) // left to right
		for (var pos = this.home.left; pos !== this.home; pos = pos.left) // right to left
		{
			// console.log(pos.count);
			if (LowCount > pos.count)
			{
				// return immediate when we find a column with zero or only one cell
				if (pos.count < 1) return pos;

				LowCount = pos.count;
				LowCountCol = pos;
			}
		}
		return LowCountCol;
	},

	// The Algorithm X itself - Leon's implementation
	// Return true if success, false if not.
	// In terms Sudoku,
	//     DLX col === constraint
	//     DLX row === candidate
	algoX : function (solution)
	{
		// 1. If the matrix A is empty, the problem is solved; terminate successfully.
		// In terms Sudoku,
		//     This is a recursive function. If the function is invoked with no constraints then the current solution set it the solution.
		if (this.home === this.home.right) return true;

		// 2. Otherwise choose a column c (deterministically).
		// In terms Sudoku,
		//     Choose a constraint to work with.
		var WorkingColumn = this.chooseCol();
		// console.log('Choosing column ' + WorkingColumn.col + ' with ' + WorkingColumn.count + ' elements.');

		// If the lowest number of 1s in any column is zero then this branch is unsuccessfully.
		// In terms Sudoku,
		//     If there is no way to satisfy a constraint, then current solution set is invalid.
		if (WorkingColumn.count === 0) return false;

		this.cover(WorkingColumn);

		// 3. Choose a row r such that A[r,c] = 1 (nondeterministically).
		// In terms Sudoku,
		//     Basically loop through each possible candidate for the currently selected constraint.
		for (var rowpos = WorkingColumn.down; rowpos !== WorkingColumn; rowpos = rowpos.down)
		{
			// console.log('In column ' + WorkingColumn.col + ', check row ' + rowpos.rowHeader.row + '.');

			// 4. Include row r in the partial solution.
			// In terms Sudoku, 
			//     Assume candidate is part of the valid solution
			solution.push(rowpos.rowHeader);

			// 5. For each column j such that A[r,j] = 1,
			//      for each row i such that A[i,j] = 1,
			//          delete row i from matrix A;
			//      delete column j from matrix A.
			// In terms Sudoku,
			//    Remove all other constraints satisfied by this candidate,
			//    Remove all candidates that can also satisfy those removed constraints.
			for (var pos = rowpos.right; pos !== rowpos; pos = pos.right)
			{
				if (pos.col === -1) continue;
				this.cover(pos.colHeader);
			}

			// 6. Repeat this algorithm recursively on the reduced matrix A.
			// console.log('Recursion');
			if (this.algoX(solution))
				return true;

			// Backtrack
			// In terms Sudoku,
			//     Backtrack assumption from #4
			for (var pos = rowpos.right; pos !== rowpos; pos = pos.right)
			{
				if (pos.col === -1) continue;
				this.uncover(pos.colHeader);
			}
			solution.pop();
		}
		this.uncover(WorkingColumn);
		return false;
	}
}
